//
//  SearchMatrix.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/8.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  240. 搜索二维矩阵 II

import UIKit

/*
 240. 搜索二维矩阵 II
 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

 每行的元素从左到右升序排列。
 每列的元素从上到下升序排列。
 示例:

 现有矩阵 matrix 如下：

 [
   [1,   4,  7, 11, 15],
   [2,   5,  8, 12, 19],
   [3,   6,  9, 16, 22],
   [10, 13, 14, 17, 24],
   [18, 21, 23, 26, 30]
 ]
 给定 target = 5，返回 true。

 给定 target = 20，返回 false。
 */

class SearchMatrix: NSObject {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        
        //可以利用矩阵的性质  从左下角开始查找
        /*eg: 要查找元素5。
        
            从左下角18开始，
            18>5，向上查；
            10>5，向上查；
            3<5，向右查；
            6>5，向上查；
            找到目标元素
        */
        
        let matrix = [
          [1,   4,  7, 11, 15],
          [2,   5,  8, 12, 19],
          [3,   6,  9, 16, 22],
          [10, 13, 14, 17, 24],
          [18, 21, 23, 26, 30]
        ]

        var subcoatIndex = 0
        
        for index in 0 ..< matrix.count {
            let subArr = matrix[matrix.count - 1 - index]
            
            for index2 in subcoatIndex ..< subArr.count{
                if subArr[index2] == target {
                    return true
                }else if subArr[index2] < target {
                    //向右查找
                    continue
                }else if subArr[index2] > target {
                    //记录当前位置 向上查找
                    subcoatIndex = index2
                    break
                }
            }
        }
        
        return false
    }
}
